HW#2 --- last modified February 06 2019 04:19:16..

Solution set.

Due date: Mar 9

Files to be submitted:
  Hw2.zip

Purpose: To reason about the hill-climbing, simulated annealing, and genetic algorithms. To code the minimax algorithm with alpha-beta pruning in a specific context.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Students should be able to explain the advantages and disadvantages of hill climbing.

LO8 -- Students should be able to explain the advantages and disadvantages of alpha-beta pruning.

Specification:

This homework consists of a written component and a coding component. Files for both components should be submitted in your Hw2.zip file along with a readme.txt with any additional instructions, a list of your team mates and their IDs. For the written part, please do the following problems and submit them in a file Hw2.pdf within the Hw2.zip file. Each of these problems is related to the 4-queens problem.

1. Start with all four queens on the bottom row. A successor board to a given board is one where one (and only one) of the queens has moved to a different row. (a) work out the the number of attacking queens for the initial board. (b) Let `r_i` be the row where the queen in the `i` column lives. Define the board number to be `sum_{i=1}^4 r_i cdot 4^i`. (b) Draw the successor board to the initial board with as few attacking queens as possible. If there is more than one board with the same number of attacking queens choose the one of smallest board number. (c) draw the successor of this successor of lowest board number with the fewest attacking queen. (d) draw the successor of this of lowest board number. After step (d), when I did this, the results board was a solution.
2. Draw a board which is not a solution to the 4-queens problem, but such that moving any single queen in its column doesn't reduce the number of attacking queens.
3. Suppose you started with the two starting boards given by (1) and (2) and were doing 2-local beam search. Assume we are breaking ties by choosing boards of least board number. (a) Draw the two best successor boards for each of these two boards. From these four boards, circle the best two. Call these two boards the successors of the local beam round. (b) Taking these two boards, compute and draw the successors of the next round.
4. Randomly generate 2 boards by rolling dice and positioning queens in the row given by the dice number (if you get a dice roll bigger than 4 re-roll). (a) For each board compute its number of attacking queens, which we will call `B_i`, and write it down. Let `Total = sum_i B_i`. (b) Do the following three times: (i) Use a random number generator to pick two numbers between 1 and Total. Write these numbers down. For each number, if it less than or equal to `B_1` draw Board 1 otherwise draw Board 2. (ii) For each pair of boards roll a die to pick a cross over point between 1 and 3, if the number is bigger than 3, reroll. (iii) Using this cross-over point, draw two child boards. (c) Circle the best two boards you got in (b). These boards could be used in the next round of this genetic algorithm, but you can stop here.

For the coding part of this assignment I would like you to write a Python program, connect_earthquake.py that plays a variant of the popular Connect Four game. This variant I call Connect Earthquake. It is played on a board with 7 slots, each of arbitrary height. As with the Connect Four game, players take turns dropping their pieces into one of the seven slots; however, in a given round, after both players have gone, a six-sided die is rolled, on a 1 an earthquake happens, and the last row of the board is deleted; on a 2, 3,4,5,6 nothing happens. After the check-for-earthquakes roll, play proceeds to next round. A check for a winner is done immediately after each player goes (before any earthquake checks). If a player has four in a row, either vertically, horizontally, or diagonally they win.

Your program will be run from the command line by the grader with a line like:

python connect_earthquake.py

Would you like to go first (y/n)?

It should then prompt:

Should I tell you when earthquake happen (y/n)?
(If not, each round, I will ask you if an earthquake happened)

This option makes it easier to play two people's programs against each other. The first player's pieces are X's, the second player's are O's. At which point an initial board is drawn. To prompt for a move your program should write:

Please enter a slot from 1 to 7 for your move:

If you answered 'y' to the earthquake question, your Python program should use a random generator to handle earthquake checks. Otherwise, after your move, it will prompt:

Did an earthquake happen (y/n)?

Here is an example transcript of a connect_earthquake game:

Would you like to go first (y/n)? y
Should I tell you when earthquake happen (y/n)?
(If not, each round, I will ask you if an earthquake happened)y
| | | | | | | |
|1|2|3|4|5|6|7|
Please enter a slot from 1 to 7 for your move:4
Board After Your Move:
| | | | | | | |
| | | |X| | | |
|1|2|3|4|5|6|7|
Board After My Move:
| | | | | | | |
| | |O|X| | | |
|1|2|3|4|5|6|7|
Board After Earthquake Check:
| | | | | | | |
| | |O|X| | | |
|1|2|3|4|5|6|7|
Please enter a slot from 1 to 7 for your move:4
Board After Your Move:
| | | | | | | |
| | | |X| | | |
| | |O|X| | | |
|1|2|3|4|5|6|7|
Board After My Move:
| | | | | | | |
| | | |X| | | |
| | |O|X|O| | |
|1|2|3|4|5|6|7|
Board After Earthquake Check:
| | | | | | | |
| | | |X| | | |
|1|2|3|4|5|6|7|
.... (many moves omitted)
Board After My Move:
| | | | | | | |
| | | | |O|O| |
| | | |O|X|X| |
| | |O|X|X|O|X|
| |O|X|X|O|O|X|
|1|2|3|4|5|6|7|
I win!!! Game over!

When the game completes your program should return to the command prompt. Your program should draw boards after each ply as in the above example. To make its move, your computer player should run the expectminimax (a variant of minimax described on page 178 of our book) algorithm with alpha beta pruning. At the top of your connect_earthquake.py program you should clearly say where to find the code for expectiminimax and alpha-beta pruning. This completes the describe of the homework

Point Breakdown